#include <iostream>
#include <string>

using namespace std;

template<typename T>
class SinglyLinkedList {
public:
  struct ListNode {
    T _data;
    ListNode* _next;

    explicit ListNode(T val) : _data(val), _next(NULL) {}
  };

  SinglyLinkedList() : _head(NULL) {}
  ~SinglyLinkedList() {
    while (_head) {
      ListNode* t = _head;
      _head = _head->_next;
      delete t;
    }
  }

  friend ostream& operator<<(ostream& os, const SinglyLinkedList<T>& list) {
    ListNode* t = list._head;
    while (t) {
      os << t->_data << " ";
      t = t->_next;
    }
    return os;
  }

  SinglyLinkedList& prepend(T val) {
    ListNode* t = new ListNode(val);
    t->_next = _head;
    _head = t;
    return *this;
  }

  SinglyLinkedList& reverse() {
    if (_head != NULL) {
      ListNode* p = _head->_next;
      _head->_next = NULL;

      while (p) {
	ListNode* t = p;
	p = p->_next;
	t->_next = _head;
	_head = t;
      }
    }
    return *this;
  }

  T mth_to_last(size_t m) {
    ListNode* left = _head;
    ListNode* right = _head;

    for (size_t i = 0; i < m; i++) {
      if (right->_next != NULL) {
	right = right->_next;
      }
      else {
	throw "List doesn't have enough elems";
      }
    }

    while (right->_next != NULL) {
      left = left->_next;
      right = right->_next;
    }
    return left->_data;
  }

private:
  ListNode* _head;

  // hiden funcs
  SinglyLinkedList(const SinglyLinkedList&);
  SinglyLinkedList& operator=(const SinglyLinkedList&);
};

int main() {
  SinglyLinkedList<int> t;
  cout << "Empty list:" << endl;
  cout << t << endl;

  cout << "Prepend 1 2 3 4 5" << endl;
  cout << t.prepend(1).prepend(2).prepend(3).prepend(4).prepend(5) << endl;

  cout << "Reverse the list" << endl;
  cout << t.reverse() << endl;

  cout << "0th to last is " << t.mth_to_last(0) << endl;
  cout << "1st to last is " << t.mth_to_last(1) << endl;
  cout << "4th to last is " << t.mth_to_last(4) << endl;

  try {
    t.mth_to_last(5);
  }
  //catch (string& str) {
  catch (char* str) {
    cout << "5th to last is " << str << endl;
  }
  catch (...) {
    cout << "Unhandled exception" << endl;
  }
  return 0;
}
